#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

int main()
{
	Heap h;
	HeapInit(&h);
	int arr[] = { 15,18,19,25,34,28,65,27,49,37 };
	for (int i = 0;i < sizeof(arr) / sizeof(arr[0]);i++)
	{
		HeapPush(&h, arr[i]);
	}
	HeapPrint(&h);

	HeapPop(&h);
	HeapPrint(&h);

	HeapPush(&h, 100);
	HeapPush(&h, 40);
	HeapPrint(&h);
	HeapPop(&h);
	HeapPrint(&h);

	return 0;
}

//剑指 Offer 40. 最小的k个数
////难度简单
////输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，
////则最小的4个数字是1、2、3、4。
////示例 1：
////输入：arr = [3, 2, 1], k = 2
////输出：[1, 2] 或者[2, 1]
////示例 2：
////输入：arr = [0, 1, 2, 1], k = 1
////输出：[0]
////限制：
////? 0 <= k <= arr.length <= 10000
////? 0 <= arr[i] <= 10000
//
///**
// * Note: The returned array must be malloced, assume caller calls free().
// */
//    void justDown(int* arr, int n, int root)//大堆下调
//{
//    int father = root;
//    int child = father * 2 + 1;//默认左孩子大
//    while (child < n)
//    {
//        if (child + 1 < n && arr[child] < arr[child + 1])
//        {  // 如果右孩子存在且右孩子比左孩子大
//            child++;
//        }
//        if (arr[father] < arr[child])
//        {
//            int tmp = arr[father];
//            arr[father] = arr[child];
//            arr[child] = tmp;
//
//            father = child;
//            child = father * 2 + 1;
//        }
//        else
//        {
//            break;
//        }
//    }
//}
//int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize) {
//    *returnSize = k;
//    if (k == 0)//回头处理k==0
//    {
//        return NULL;
//    }
//    int* retArr = (int*)malloc(sizeof(int) * k);
//    for (int i = 0;i < k;i++)
//    {
//        retArr[i] = arr[i];
//    }
//    for (int i = (k - 1 - 1) / 2;i >= 0;i--) //建堆的for写法
//    {
//        justDown(retArr, k, i);
//    }
//    for (int j = k;j < arrSize;j++)
//    {
//        if (arr[j] < retArr[0])
//        {
//            retArr[0] = arr[j];
//            justDown(retArr, k, 0);
//        }
//    }
//    //*returnSize = k; 写到这发现有个测试用例跑不了，到上面处理一下
//    return retArr;
//}


////剑指 Offer II 076. 数组中的第 k 大的数字
////难度中等
////
////给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
////
////请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//void Swap(int* px, int* py)
//{
//    int tmp = *px;
//    *px = *py;
//    *py = tmp;
//}
//
//void justDown(int* arr, int n, int root)//大堆下调
//{
//    int father = root;
//    int child = father * 2 + 1;//默认左孩子大
//    while (child < n)
//    {
//        if (child + 1 < n && arr[child] < arr[child + 1])
//        {  // 如果右孩子存在且右孩子比左孩子大
//            child++;
//        }
//        if (arr[father] < arr[child])
//        {
//            Swap(&arr[father], &arr[child]);
//
//            father = child;
//            child = father * 2 + 1;
//        }
//        else
//        {
//            break;
//        }
//    }
//}
//
//int findKthLargest(int* nums, int numsSize, int k) {
//    for (int i = (numsSize - 1 - 1) / 2;i >= 0;i--) //建堆的for写法
//    {
//        justDown(nums, numsSize, i);
//    }
//    // 删除数据（参考前面文章堆的pop）
//    for (int i = 1;i <= k - 1;i++)
//    {
//        Swap(&nums[0], &nums[numsSize - i]);
//        justDown(nums, numsSize - i, 0);//删除多少个numsize-多少个
//    }
//    return nums[0];
//}